// GlobalRegAllocator.cpp 
// Implement class GlobalRegAllocator
//Transplanted by lixiaolong.
//The 7th physical register has the most used vreg mapped all the time.
#include "crossbit/GlobalRegAllocator.h"
#include "crossbit/VBlock.h"
#include "crossbit/VInst.h"

using namespace crossbit;

void GlobalRegAllocator::init(VBlock *vb)
{
				vinst_seq = 0;
    ra_cal_treg=0;
    global=false;
				struct RegUsage ru;
				ru.status = RegAllocator::FREE;
				ru.mapped_to = -1;
				ru.inst = 0;
				for (XTRegNum i = 0; i < ra_num_of_reg; ++i)
				{
								ra_reg_table[i]=ru;
				}
			 UTIL::XTMemset(ra_vreg_spilledIn,0,sizeof(ra_vreg_spilledIn));
		 CollectUseFrequency(vb);   //collect for Global Frequency information. 
}

void GlobalRegAllocator::CollectUseFrequency(VBlock *vb)
{
		g_use_frequency_tbl.clear();
		VBlock::vb_iterator vb_I=vb->begin(),vb_E=vb->end();
		for(;vb_I!=vb_E;vb_I++)
	{
		VInst *inst=*vb_I;
	 XTInt32 n=inst->getOperandNum();
		for(XTInt32 i=1;i<=n;i++)
 	{
		Operand oprnd=inst->getOperand(i);
		XTRegNum r;
		if(oprnd.type==Operand::VREG_USE && oprnd.reg>0)
		{	
		r=oprnd.reg;
	 g_use_frequency_tbl[r]++;
		}
	else if(oprnd.type==Operand::VREG_DEF)
		{
			r=oprnd.reg;
			g_use_frequency_tbl[r]=1;
		}
		}
	}
		XTRegNum mostvreg=0;
		XTInt32 fre=0,temp=0;
		std::map<XTRegNum,XTInt32>::iterator use_I=g_use_frequency_tbl.begin(),use_E=g_use_frequency_tbl.end();
		for(;use_I!=use_E;use_I++)
	{
			temp=use_I->second;
		 if(temp>fre)
			{
				fre=temp;
				mostvreg=use_I->first;
			}
	}
		if(mostvreg!=0 && fre>=3)
		{
   global=true;
			XTRegNum alloc=7;
			ra_reg_table[alloc].status=ALLOCATED;
			ra_reg_table[alloc].mapped_to=mostvreg;
		}
}
void GlobalRegAllocator::phaseTask()
{
}

// Allocate target register for virtual register
XTRegNum GlobalRegAllocator::regAlloc(XTRegNum vreg, RegAccessMode mode)
{
   //printf("This is regAlloc calling!\n");
				XTRegNum alloc;
				for(XTRegNum i=0;i<ra_num_of_reg;i++)
									{
											if(ra_reg_table[i].status==ALLOCATED && ra_reg_table[i].mapped_to==vreg)
										{
            if(ra_vreg_spilledIn[vreg]==false&&mode==USE)
            {
              regSpillIn(vreg,i);
              ra_vreg_spilledIn[vreg]=true;
            }
												  ra_reg_table[i].inst=vinst_seq;
             // printf("1 %d vreg alloc %d treg\n",vreg,i);
														return i;
									 }
									} 
				for(XTRegNum i=0;i<ra_num_of_reg;i++)
								{  
										if(ra_reg_table[i].status==FREE)
           {
            if(ra_vreg_spilledIn[vreg]==false&&mode==USE)
           { 
            regSpillIn(vreg,i);
											 ra_vreg_spilledIn[vreg]=true;
            }
												ra_reg_table[i].status=ALLOCATED;
												ra_reg_table[i].mapped_to=vreg;
												ra_reg_table[i].inst=vinst_seq;
         //   printf("2 %d vreg alloc %d treg\n",vreg,i);
												return i;
											}
								} 
	
           // ra_cal_treg=7;
           // find ALLOCATED target register whose mapped virtual regiser 
												// using vreg%8 to allocate the target regs.
												for(XTInt32 cn=0;cn<9;cn++)
												{
            if (global) 
               {
                 if (ra_cal_treg==7)
                    ra_cal_treg=(ra_cal_treg+1)%8;
               }
												struct RegUsage tru=ra_reg_table[ra_cal_treg];
											if (tru.status!=RegAllocator::ALLOCATED||tru.inst==vinst_seq)//RESERVED register can't be used&&The treg who is using in the current instruction.
														ra_cal_treg=(ra_cal_treg+1)%8;
											  else
                {
												     break;
                }
												}
												alloc=ra_cal_treg;
            ra_cal_treg=(ra_cal_treg+1)%8;
												regSpillOut(alloc);
 			if (mode==USE)
   {
		 	regSpillIn(vreg, alloc);
				ra_vreg_spilledIn[vreg]=true;
   }
				ra_reg_table[alloc].status = ALLOCATED;
				ra_reg_table[alloc].mapped_to = vreg;
				ra_reg_table[alloc].inst = vinst_seq; 
  //  printf("3 %d vreg alloc %d treg\n",vreg,alloc);
    return alloc;
  
}

// Force allocate target register "expect" to "vreg"
//
// Algorithms:
//  if (vreg is already allocated to expect)
//	return immediately
//  else 
//	empty "expect" register for "Vreg";
//	if (vreg is currently allocated to another target register)
//	    move it to "expect"
//	if (vreg is spilled)
//	    load vreg from spill pool to expect
//	...
// 
XTRegNum GlobalRegAllocator::regAllocForce(XTRegNum vreg, XTRegNum expect, RegAccessMode mode)
{
//    printf("This is regAllocForce calling!\n");
    RegUsage etru=ra_reg_table[expect];
				assert(etru.status != RegAllocator::RESERVED); // dead-lock
				
			  if (etru.status == RegAllocator::ALLOCATED) 
								{
            if(etru.mapped_to==vreg)
           {
            ra_reg_table[expect].inst=vinst_seq;
            if(ra_vreg_spilledIn[vreg]==false&&mode==USE)
           {
            regSpillIn(vreg,expect);
            ra_vreg_spilledIn[vreg]=true;
           }
          //  printf("******1 %d vreg alloc %d treg\n",vreg,expect);
            return expect;
           }
            assert(expect!=7);
            regSpillOut(expect);
        }
            for(XTRegNum i=0;i<ra_num_of_reg;i++)
												{
														if(ra_reg_table[i].status==ALLOCATED&&ra_reg_table[i].mapped_to==vreg)
             {
                (*ra_cb_reg_to_reg)(i,expect);
                ra_reg_table[expect].status=ALLOCATED;
                ra_reg_table[expect].inst=vinst_seq;
																ra_reg_table[expect].mapped_to=vreg;
                ra_reg_table[i].status=FREE;
                ra_reg_table[i].mapped_to=-1;
           // printf("******2 %d vreg alloc %d treg\n",vreg,expect);
                return expect;
												}
							   	}
        ra_vreg_spilledIn[vreg]=false;
								if (mode==USE) 
											{
            	regSpillIn(vreg, expect);
             ra_vreg_spilledIn[vreg]=true;
           }

							 ra_reg_table[expect].status=ALLOCATED;
								ra_reg_table[expect].mapped_to=vreg;
        ra_reg_table[expect].inst=vinst_seq;
      //  printf("******3 %d vreg alloc %d treg\n",vreg,expect);
				return expect;
}

// Force "vreg" NOT to be allocated to "except"
//
// Algorithm:
//	if vreg is already allocated and it's not "except"
//	    return immediately
//	else 
//	    "reserve" "except" register
//	    alloc = regAlloc(vreg, mode)
//	    "release" "except" register
//
XTRegNum GlobalRegAllocator::regAllocForceExcept(XTRegNum vreg, XTRegNum except, RegAccessMode mode)
{
  //  printf("This is regAllocForceExcept calling!\n");
    XTInt32 temp=ra_reg_table[except].status;
    XTRegNum alloc;
				if (temp== ALLOCATED && ra_reg_table[except].mapped_to == vreg)
			{				
     regSpillOut(except);
    //ra_reg_table[except].mapped_to=-1;
     temp=FREE;
   }
     ra_reg_table[except].status=RESERVED;
     alloc=regAlloc(vreg,mode);
     ra_reg_table[except].status=temp;
								/*bool reserve = false;
								if (temp!= RegAllocator::RESERVED)
								{
												regAllocReserve(except);
												reserve = true;
								}

								alloc = regAlloc(vreg, mode);

								if (reserve)
												regAllocRelease(except);*/
    // printf("!!!1 %d vreg alloc %d treg,except %d\n",vreg,alloc,except);
		 		return alloc;
}

void GlobalRegAllocator::regAllocReserve(XTRegNum treg)
{
    //printf("This is regAllocReserve calling!\n");
				struct RegUsage &tru = ra_reg_table[treg];
				assert(tru.status != RegAllocator::RESERVED && "regAllocReserve"); 
			 if(tru.inst==vinst_seq) printf("Can't reserve the reg here!!\n");
   	if (tru.status == RegAllocator::ALLOCATED)
								regSpillOut(treg);
				tru.status = RegAllocator::RESERVED;
    tru.mapped_to = 0;
				return;
}


void GlobalRegAllocator::regAllocRelease(XTRegNum treg)// Release only affect the RESERVED Registers.
{
   // printf("This is regAllocRelease calling!\n");
				struct RegUsage &tru = ra_reg_table[treg];
				assert(tru.status == RESERVED);
				tru.status = RegAllocator::FREE;
				return;
}

void GlobalRegAllocator::regSpillIn(XTRegNum vreg, XTRegNum treg)
{
		(*ra_cb_spill_in)((XTMemAddr)(ra_spill_pool+vreg), treg);
}


XTRegNum GlobalRegAllocator::regSpillOut(XTRegNum treg)
{
		//	printf("regSpillOut\n");
				assert(ra_reg_table[treg].status == RegAllocator::ALLOCATED);	

				XTRegNum vreg = ra_reg_table[treg].mapped_to;

				(*ra_cb_spill_out)(treg, (XTMemAddr)(ra_spill_pool+vreg));
   // ra_vreg_spilled[vreg]=true;
    ra_vreg_spilledIn[vreg]=false;
				return treg;
}
